package leetcode.top100;

import offerbook.Code09_Fibonacci;
import offerbook.Code09_FillRectangle;
import offerbook.Code09_FrogJumpStep;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * <p>
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * <p>
 * 注意：给定 n 是一个正整数。
 *
 * 分析：本质就是斐波那契数问题，更多相关问题见
 * @see Code09_Fibonacci
 * @see Code09_FrogJumpStep
 * @see Code09_FillRectangle
 * @since 2019/12/3 0003 下午 10:11
 */
public class Code70_ClimbStep_爬楼梯 {

    /**
     * 方式1：递归，重复计算，时间O(2^n)
     */
    public int climbStairs(int n) {
        if(n <= 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        return climbStairs(n-1)+climbStairs(n-2);

    }

    public static void main(String[] args) {
        int n = 2;
        int []arr = new int[n+1];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;
        climbStairs1(n,arr);
    }
    /**
     * 方式2：带有记忆的递归
     */
    public static int  climbStairs1(int n,int []arr) {
       if(n <= 2 || arr[n] > 0){
           return arr[n];
       }

        arr[n] =  climbStairs1(n-1,arr)+climbStairs1(n-2,arr);
        return arr[n];
    }

    /**
     * 方式3：DP1
     */
    public int climbStairs3(int n) {
        if(n <= 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int []dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i<=n ; i++){
           dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
    /**
     * 方式4：DP2
     */
    public int climbStairs4(int n) {
        if(n <= 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        int f1 = 1;
        int f2 = 2;
        //if n = 2, return 2
        int f3 = 2;
        for(int i = 3; i<=n ; i++){
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }
    /**
     * TODO 见进阶班
     * 方式5：o(logn)，利用矩阵特性：
     * 方式6：求特征值 ，求通式,o(nlogn):
     */
}
